package com.example.tinxi.data.structure.tree;

/**
 * 字典树(TrieTree)
 * @author tinxi
 * @create 2019-01-14 15:11:59
 *
 *
 * 1）查询
 * Trie树是简单但实用的数据结构，通常用于实现字典查询。我们做即时响应用户输入的AJAX搜索框时，就是Trie开始。本质上，Trie是一颗存储多个字符串的树。
 * 相邻节点间的边代表一个字符，这样树的每条分支代表一则子串，而树的叶节点则代表完整的字符串。
 * 和普通树不同的地方是，相同的字符串前缀共享同一条分支。下面，再举一个例子。
 * 给出一组单词，inn, int, at, age, adv, ant, 我们可以得到下面的Trie：
 *
 * 每条边对应一个字母。
 * 每个节点对应一项前缀。叶节点对应最长前缀，即单词本身。
 * 单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支，root->i->in。同理，ate, age, adv, 和ant共享前缀”a”，所以他们共享从根节点到节点”a”的边。
 * 每条边对应一个字母。
 * 每个节点对应一项前缀。叶节点对应最长前缀，即单词本身。
 * 单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支，root->i->in。同理，ate, age, adv, 和ant共享前缀”a”，所以他们共享从根节点到节点”a”的边。
 * 查询操纵非常简单。比如要查找int，顺着路径i -> in -> int就找到了。
 *
 *
 * 搭建Trie的基本算法也很简单，无非是逐一把每则单词的每个字母插入Trie。
 * 插入前先看前缀是否存在。如果存在，就共享，否则创建对应的节点和边。
 * 比如要插入单词add，就有下面几步：
 *  1.考察前缀”a”，发现边a已经存在。于是顺着边a走到节点a。
 *  2.考察剩下的字符串”dd”的前缀”d”，发现从节点a出发，已经有边d存在。于是顺着边d走到节点ad
 *  3.考察最后一个字符”d”，这下从节点ad出发没有边d了，于是创建节点ad的子节点add，并把边ad->add标记为d。
 *
 * 2）一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析.
 * 先用trie树统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平均长度）；
 * 然后是用小顶堆找出出现最频繁的前10个词，时间复杂度是O(n*lg10)。
 * 3）1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。
 * 使用hash_map或者trie树。
 * 比如trie树，在构建trie树的过程中，如果某个字符串已经存在于trie中则不输出，否则输出到文本中，这样就可以得到不重复的字符串。
 * hash_map的速度会要快一些，因为在添加一个字符串的时候，hashmap直接用哈希函数就能定位，然后选择是否写入文件，但是trie树需要在子节点中比较。
 * trie树对hashmap的优势是，在大量重复的单词中，trie树需要的内存会低一些。
 */
public class TrieTree {
	private TrieNode root;

	public TrieTree() {
		this.root = new TrieNode();
	}

	/**
	 * 创建字典树
	 * @param str  待插入的内容
	 * @param node 字典树
	 * @return
	 */
	public static void createTrieTree(String str, TrieNode node) {
		// ascii A>>65, a>>97
		char[] chars = str.toCharArray();
		for (int i = 0; i < chars.length; i++) {
			int loc = chars[i] - 'a';   // 转成0~25中间的数字, 将字母转换成数组的索引
			if (node.childrenNodes[loc] == null) { // 如果没有就直接创建子节点
				node.childrenNodes[loc] = new TrieNode();
				node.childrenNodes[loc].ch = chars[i];
			}
			node = node.childrenNodes[loc];  // 类似于递归, 将当前子节点当成下一层级的父节点
		}
		node.isEndNode = true;
	}

	/**
	 * 查找内容
	 * @param str  被查找的内容
	 * @param node 字典树
	 * @return
	 */
	public static boolean find(String str, TrieNode node) {
		char[] chars = str.toCharArray();
		for (int i = 0; i < chars.length; i++) {
			int loc = chars[i] - 'a';
			if (node.childrenNodes[loc] == null) {
				return false;
			}
			node = node.childrenNodes[loc];
		}
		return node.isEndNode;
	}

	public static void main(String[] args) {
		String[] s = {"java", "php", "tomcat", "js", "photo", "banana"};
		TrieNode root = new TrieNode();
		for (String s1 : s) {
			createTrieTree(s1, root);
		}

		System.out.println(123123);
		System.out.println(find("java", root));
		System.out.println(find("jav", root));




	}

}